package leetcode.binarysearch;

import java.util.Arrays;

//153. 寻找旋转排序数组中的最小值
public class FindMin {

    public static void main(String[] args) {
        int[] data = {3, 4, 5, 1, 2};
        System.out.println(findMin2(data));
    }

    public int findMin(int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int x : nums) {
            min = Math.min(x, min);
        }
        return min;
    }

    //二分
    public static int findMin2(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > nums[right]) {
                //最小值在右边
                left = mid + 1;
            } else {
                //最小值在左边
                right = mid;
            }

        }
        //right和left重合
        return nums[right];
    }


    //暴力
    public int findMinP(int[] nums) {
        Arrays.sort(nums);
        return nums[0];
    }

    //二分
    public int findMinP2(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        while (l<r){
            int mid = l+(r-l)/2;
            if (nums[mid]>nums[r]){
                //说明最小值在右边
                l = mid+1;
            }else {
                r = mid;
            }
        }
        //最后指针一定重合
        return nums[l];
    }
}
